package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class fiftenn2 {
    public static List<Integer> findSubstring(String s, String[] words) {
        int m=s.length();
        int n=words.length;
        int p=words[0].length();
        List<Integer> list=new ArrayList<>();
        if(m<n*p){
            return list;
        }
        HashMap<String,Integer> HashMap=new HashMap<>();
        for(int i=0;i<n;i++){
            String in=words[i];
            HashMap.put(in,HashMap.getOrDefault(in,0)+1);
        }

        int left;
        int right;
        //处理滑动窗口执行的个数
        for(int i=0;i<p;i++){
            HashMap<String,Integer> HashMap1=new HashMap<>();
            int count=0;
            for(left=i,right=i;right+p<=m;right+=p){
                String in1=s.substring(right,right+p);
                //进窗口
                HashMap1.put(in1,HashMap1.getOrDefault(in1,0)+1);
                count++;
                //判断
                if(count==n){
                    //更新结果
                    if(HashMap.equals(HashMap1)){
                        list.add(left);
                    }
                    //出窗口
                    String out=s.substring(left,left+p);
                    HashMap1.put(out,HashMap1.get(out)-1);
                    if(HashMap1.get(out)==0){
                        HashMap1.remove(out);
                    }
                    left+=p;
                    count--;

                }

            }

        }
        return list;

    }
    public static void main(String[] args) {
//        s = "barfoothefoobarman", words = ["foo","bar"]
        String s="lingmindraboofooowingdingbarrwingmonkeypoundcake";
        String[] words={"fooo","barr","wing","ding","wing"};
        List<Integer> substring = findSubstring(s, words);
        System.out.println(substring);


    }
}
